package com.berchen.offer;

/**
 *输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
 * 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
 */
public class Test01 {
    public boolean hasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null){
            return false;
        }
        if(root1==null&&root2!=null){
            return false;
        }
        boolean flag=false;
        // root1和root2相等 根节点 直接两个树进行比较
        if(root1.val== root2.val){
            flag=subIsAble(root1,root2);
        }
        if(!flag){
            // 遍历root1根节点左子树
            flag=hasSubtree(root1.left,root2);
            if(!flag){
                // 有子树 直到找到相同的根节点  然后才调用下面的方法
                flag=hasSubtree(root1.right,root2);
            }
        }return flag;
    }

    /**
     * 判断两棵树是否相同
     * @param root1 树1 的根节点
     * @param root2 树2 的根节点
     * @return
     */
    public boolean subIsAble(TreeNode root1,TreeNode root2){
        if(root2==null){
            return true;
        }
        if(root1==null&&root2!=null){
            return false;
        }
        if(root1.val== root2.val) {
            return subIsAble(root1.left, root2.left)&&subIsAble(root1.right, root2.right);
        }
        return false;
    }
}
